package zcw.com.lib_leet_code;

/**
 * Created by 朱城委 on 2022/1/17.<br><br>
 *
 * 中等：加油站
 */
public class Topic134 {

    public static void main(String[] args) {
        BaseSolution solution = new Solution2();

        int[] gas = new int[] {1,2,3,4,5};
        int[] cost = new int[] {3,4,5,1,2};
        System.out.println(solution.canCompleteCircuit(gas, cost));

        gas = new int[] {2,3,4};
        cost = new int[] {3,4,3};
        System.out.println(solution.canCompleteCircuit(gas, cost));
    }

    private interface BaseSolution {
        int canCompleteCircuit(int[] gas, int[] cost);
    }

    /**
     * 此解法超时
     */
    private static class Solution1 implements BaseSolution {

        @Override
        public int canCompleteCircuit(int[] gas, int[] cost) {
            for(int i = 0; i < gas.length; i++) {
                if(helper(gas, cost, i)) {
                    return i;
                }
            }
            return -1;
        }

        private boolean helper(int[] gas, int[] cost, int index) {
            int n = gas.length;

            int counter = 1;
            int numOfGas = gas[index];
            int numOfCost = cost[index];
            while (numOfGas >= numOfCost) {
                if(counter == n) {
                    return true;
                }

                int tempIndex = (index + counter++) % n;
                numOfGas += gas[tempIndex];
                numOfCost += cost[tempIndex];
            }

            return false;
        }
    }

    private static class Solution2 implements BaseSolution {

        @Override
        public int canCompleteCircuit(int[] gas, int[] cost) {
            int n = gas.length;

            int i = 0;
            while (i < n) {
                int counter = 1;
                int numOfGas = gas[i];
                int numOfCost = cost[i];

                while (numOfGas >= numOfCost) {
                    if(n == counter) {
                        return i;
                    }

                    int index = (i + counter) % n;
                    numOfGas += gas[index];
                    numOfCost += cost[index];

                    counter++;
                }

                i += counter;
            }

            return -1;
        }
    }
}
